package com.peng.leetcode.dynamic;

import java.util.Arrays;

/**
 * CalculateMinimumHP
 *
 * @author: lupeng6
 * @create: 2021/1/27 10:11
 */
public class CalculateMinimumHP {

    public static void main(String[] args) {
        int[][] dungeon = {{0, 0, 0}, {-1, 0, 0}, {2, 0, -2}};
        System.out.println(new CalculateMinimumHP().calculateMinimumHP(dungeon));
    }

    /**
     * 动态规划转移方程
     * dp[i][j] = max( min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j] , 1 )
     *
     * @author lupeng6
     * @date 2021/1/27 10:14
     */
    public int calculateMinimumHP(int[][] dungeon) {
        if (dungeon == null || dungeon.length == 0) {
            return 0;
        }
        int rows = dungeon.length;
        int cols = dungeon[0].length;
        int[][] dp = new int[rows][cols];

        // init
        for (int i = 0; i < rows; i++) {
            Arrays.fill(dp[i], Integer.MAX_VALUE);
        }

        dp[rows - 1][cols - 1] = dungeon[rows - 1][cols - 1] < 0 ? 1 - dungeon[rows - 1][cols - 1] : 1;

        for (int i = rows - 2; i >= 0; i--) {
            int cost = dungeon[i][cols - 1];
            int curr = Math.max(dp[i + 1][cols - 1] - cost, 1);
            dp[i][cols - 1] = curr;
        }

        for (int i = cols - 2; i >= 0; i--) {
            int cost = dungeon[rows - 1][i];
            int curr = Math.max(dp[rows - 1][i + 1] - cost, 1);
            dp[rows - 1][i] = curr;
        }

        for (int i = rows - 2; i >= 0; i--) {
            for (int j = cols - 2; j >= 0; j--) {
                int min = Math.min(dp[i + 1][j], dp[i][j + 1]);
                int curr = Math.max(min - dungeon[i][j], 1);
                dp[i][j] = curr;
            }
        }

        return dp[0][0];
    }
}
